350. Intersection of Two Arrays II

給定兩個整數數組 nums1 和 nums2，返回兩個數組的交集。輸出結果中的每個元素應該與其在兩個數組中出現的次數一致(也就是交集中每個元素的出現次數應等於該元素在兩個數組中最小的出現次數)，結果可以按任意順序返回。
與昨天刷到的第349題不太一樣的地方在於，349 題只需要找到兩個數組的交集(不考慮每個元素出現的次數)，而 350 題要求返回的交集元素需要考慮到每個元素出現的次數(即結果中某個元素出現的次數應等於該元素在兩個數組中最少的出現次數)。

程式碼

from collections import Counter

class Solution:
    def intersect(self, nums1, nums2):
        # 使用 Counter 來統計每個數組中元素的出現次數
        count1 = Counter(nums1)
        count2 = Counter(nums2)
        
        # 結果列表
        result = []
        
        # 遍歷 count1，檢查每個元素在 count2 中的次數，取最小值作為結果
        for num in count1:
            if num in count2:
                # 找到該元素的最小出現次數，並加入結果中
                min_count = min(count1[num], count2[num])
                result.extend([num] * min_count)
        
        return result

49. Group Anagrams

給定一組字串，請將字母異位詞（Anagrams）分組，字母異位詞指的是由相同字母組成的不同字串，例如：["eat", "tea", "tan", "ate", "nat", "bat"] 中的 "eat", "tea", "ate" 是字母異位詞。

要解決這個問題，我們需要能夠判斷兩個字串是否是異位詞。

字母排序法

將字串排序，並以排序後的字串作為判斷異位詞的依據。
優點：簡單且直觀。
時間複雜度：對每個字串進行排序需要 𝑂(𝑛 log 𝑛)整體複雜度取決於字串數量與長度。

程式碼

class Solution:
    def groupAnagrams(self, strs: List[str]) -> List[List[str]]:
        if not strs:
            return [[""]]
        hash_table = {}
        for s in strs:
            sorted_str = ''.join(sorted(s))
            if sorted_str in hash_table:
                hash_table[sorted_str].append(s)
            else:
                hash_table[sorted_str] = [s]
        return list(hash_table.values())

其他解法思路

字母計數法（使用 collections.Counter）
這種方法的原理是，對每個字串中的每個字母進行統計，並將統計結果（字母出現次數）作為鍵值，將異位詞分到同一個鍵的列表中。

• 時間複雜度分析
  時間複雜度： 𝑂(𝑁⋅𝐾)，其中 𝑁 是字串的個數，𝐾 是字串的平均長度。
  空間複雜度： 𝑂(𝑁⋅𝐾)，用來儲存每個字串的字母計數鍵和結果。

質數映射法
這種方法的原理是，將每個字母映射到不同的質數，然後將字串中所有字母對應的質數相乘作為鍵來進行比較。這樣做的原因是，質數的乘積是唯一的，可以唯一表示一個字母異位詞組合。

• 質數映射的特點
  質數的乘積是唯一的，即使字母異位詞的排列順序不同，其所有字母對應質數的乘積結果也會相同。
  利用質數的特性來進行比較，可以將字母異位詞的判斷變成常數時間的計算。

• 時間複雜度分析
  時間複雜度： 𝑂(𝑁⋅𝐾)，每個字串只需計算一遍質數乘積即可。
  空間複雜度： 𝑂(𝑁)，用來儲存每個字串的質數乘積值。